Міністерство освіти і науки України
Національний університет “Львівська політехніка”
кафедра прикладної математики
КУРСОВА РОБОТА
з курсу дискретна математика
на тему:
„Автомати з магазинною пам’яттю. Контекстно-вільні граматики”
Виконала:
студентка групи ПМ-32
Прийняв:
Львів -2006
ЗМІСТ
Вступ. Основні поняття теорії формальних мов і грамматик................................3
Означення МП-автомата……………………………………………………………….3
Варіанти МП-автоматів………………………………………………………………..6
Еквівалентність МП-автоматів і КВ-граматик……………………………………...10
Детерміновані МП-автомати…………………………………………………………16
Синтез МП-автомата………………………………….................................................21
Програмна реалізація синтезу ДМП-автомата……………………………………...23
Список використаної літератури…………………….................................................27
Основні поняття теорії формальних мов і граматик.
Для того, щоб зрозуміти теорію алгоритмічних мов, необхідно оперувати найпростішими, але найфундаментальнішими поняттями теорії формальних мов і граматик, мати чітку уяву про ієрархію мови – літера, слово, мова.
Отже, літера – це простий неподільний знак. Множина літер утворює алфавіт.
Ланцюжок (слово, стрічка) – це впорядкована скінченна послідовність літер алфавіту. ε–порожній ланцюжок, ланцюжок нульової довжини. Над ланцюжками допускаються операції конкатенації (об’єднання ланцюжків) та обертання стрічок.
Мовою LA, породженою алфавітом А, називається сукупність всіх стрічок, отриманих у даній мові. Дамо також означення граматики. Формальною породжуючою граматикою G називається четвірка <N,Т,Р,S> , де Т – скінченна не порожня множина символів, яка називається термінальним або основним словником граматики G; N – скінченна не порожня множина символів, що називається нетермінальним (допоміжним) словником граматики G, причому ТN=Ø, Т N=V –об’єднаний словник граматики G; S – початковий символ або аксіома граматики G, S – нетермінал і є головною метою граматики G; Р – скінченна множина правил граматики G, елемент цієї множини можна задати у вигляді пари (α , β); ця пара – правило виводу або правило підстановки і часто записується у вигляді α→β. Варто зауважити, що α,β{NТ}* (A*– множина всіх можливих ланцюжків над алфавітом А, A*=А0А1А2...Аn... і називається замиканням алфавіту А або повною ітерацією; є ще неповна ітерація:А+ = A* \{ε}). Правила підстановки називають також схемою граматики.
Означимо відношення G (відношення в граматиці G, надалі писатимемо без позначки внизу, коли розумітимемо про яку граматику йдеться) на множині (NT)* так: якщо αβγ – стрічка з (NT)* і β → δ – правило з Р, то αβγ αδγ. Транзитивне замикання відношення позначають через+ (φ + ψ читається: ψ виводима з φ нетривіальним чином), а його рефлексивне і транзитивне замикання: * (φ * ψ читається: ψ виводима з φ).
Існує чотири класи мов і граматик за Хомським, але ми користуватимемося класом, що містить так звані контексно-вільні мови (КВ-мови). Це – мови, що породжуються граматиками, які мають правила виводу такого виду: α→β, де αN, βV+, тобто ліві частини правил виводу мають лише один нетермінальний символ.
Означення МП-автомата
Автомат з магазинною пам’яттю—розпізнавач, який представляє собою звичайну модель синтаксичних аналізаторів контекстно-вільних мов. Автомат з магазинною пам’яттю—односторонній недетермінований розпізнавач , в потенційно нескінченній пам’яті якого елементи інформації зберігаються і використовуються так само, як патрони в магазині автоматичної зброї, тобто в кожний момент доступний тільки верхній елемент магазина. Розпізнавач такого типу зображений на рисунку 1.
А1
А2
Аn
Вхідна стрічка
(тільки читати)
Z1
Z2
...